W12. Представления графов, DFS, BFS и топологическая сортировка

Автор

Nikolai Kudasov

Дата публикации

7 апреля 2026 г.

1. Краткое содержание

1.1 Граф как модель

Графы явно кодируют связи между объектами: веб-страницы, зависимости задач, маршруты, соавторство. Типовые задачи: shortest paths, обход всех вершин (TSP и релаксации), minimum spanning trees, topological sort при ограничениях-предшествованиях.

Граф \(G=(V,E)\): конечное множество вершин (vertices / nodes) и рёбер.

  • Неориентированный граф (undirected graph): рёбра — неупорядоченные пары \(\{u,v\}\), симметрия.
  • Ориентированный граф (directed graph, digraph): рёбра — упорядоченные пары \((u,v)\).

side cluster_directed Ориентированный граф cluster_undirected Неориентированный граф u1 u v1 v u1->v1  {u,v} u2 u v2 v u2->v2  (u,v)

Смежность (adjacent): две вершины смежны, если их соединяет ребро; в ориентированном графе из \((u,v)\in E\) следует, что \(v\) — исходящий сосед \(u\), а \(u\) — входящий сосед \(v\). Путь (path) от \(s\) до \(t\) — последовательность вершин с рёбрами между соседними; простой путь (simple path) не повторяет вершины. Цикл (cycle) — путь с совпадающими началом и концом. Взвешенный граф (weighted graph) задаёт числовой вес на каждом ребре (расстояние, стоимость и т.п.); для кратчайших путей по сумме весов позже используют, например, Dijkstra’s algorithm.

1.2 Представления графов

Динамический граф поддерживает insertVertex, insertEdge, removeVertex, removeEdge, getEdge, degree, iterateNeighbors. Выбор структуры — по доминирующим операциям и плотности (density): sparse \(|E|\ll|V|^2\), dense \(|E|=\Theta(|V|^2)\).

Список рёбер (edge list): список вершин + список рёбер; простые обновления, но getEdge и degree — \(\Theta(|E|)\).

edgelist vlist Список вершин A B C elist Список рёбер x: A-B y: B-C

Списки смежности (adjacency lists): стандарт для разреженных графов; DFS, BFS и топосорт — \(\Theta(V+E)\).

Матрица смежности (adjacency matrix): \(\Theta(|V|^2)\) памяти; getEdge за \(O(1)\); хороша при плотных графах.

Сравнение при \(n=|V|\), \(m=|E|\):

Operation Edge list Adjacency lists Adjacency matrix
getEdge(u,v) \(O(m)\) \(O(\min(\deg u, \deg v))\) \(O(1)\)
degree(v) \(O(m)\) \(O(1)\)* \(O(n)\) or \(O(1)\)*
iterateNeighbors(v) \(O(m)\) \(O(\deg v)\) \(O(n)\)
insertVertex \(O(1)\) \(O(1)\) \(O(n^2)\) / \(O(1)\) amort.
removeVertex \(O(m)\) \(O(\deg v)\) \(O(n^2)\) / \(O(n)\) amort.
insertEdge \(O(1)\) \(O(1)\) \(O(1)\)
removeEdge \(O(1)\)** \(O(1)\)** \(O(1)\)
Space \(O(n + m)\) \(O(n + m)\) \(O(n^2)\)

*При явных счётчиках степеней. **При указателе на объект ребра и двусвязных списках смежности.

1.3 Обходы

Graph traversal — систематический визит достижимых вершин. Применения: connected components, reachability, cycle detection (back edges в DFS), мосты и точки сочленения и др.

1.4 Поиск в глубину (DFS)

Идея: углубляться, затем откат. Рекурсивный вариант с метками времени \(u.d\), \(u.f\) и цветами WHITE / GRAY / BLACK:

DFS(G):
1  for each vertex u in G.V:
2      u.color = WHITE;  u.π = NIL
3  time = 0
4  for each vertex u in G.V:
5      if u.color == WHITE:
6          DFS-VISIT(G, u)

DFS-VISIT(G, u):
1  time = time + 1;  u.d = time;  u.color = GRAY
2  for each v in G.Adj[u]:
3      if v.color == WHITE:
4          v.π = u
5          DFS-VISIT(G, v)
6  time = time + 1;  u.f = time;  u.color = BLACK

Сложность: со списками смежности — \(\Theta(V+E)\); с матрицей — \(\Theta(V^2)\).

Классификация рёбер в ориентированном графе: tree edge, back edge (указывает на directed cycle), forward edge, cross edge. Parenthesis theorem о вложенности интервалов \([u.d,u.f]\).

1.5 Поиск в ширину (BFS)

Очередь FIFO; уровни расстояния от источника.

BFS(G, s):
1  for each vertex u in G.V - {s}:
2      u.color = WHITE;  u.d = ∞;  u.π = NIL
3  s.color = GRAY;  s.d = 0;  s.π = NIL
4  Q = ∅;  ENQUEUE(Q, s)
5  while Q ≠ ∅:
6      u = DEQUEUE(Q)
7      for each v in G.Adj[u]:
8          if v.color == WHITE:
9              v.color = GRAY;  v.d = u.d + 1;  v.π = u
10             ENQUEUE(Q, v)
11     u.color = BLACK

Время — \(\Theta(V+E)\) со списками смежности.

BFS даёт кратчайшие пути по числу рёбер в невзвешенном графе: \(\delta(s,v)=v.d\) после обхода. Для весов BFS недостаточен — нужен Dijkstra’s algorithm.

1.6 DFS vs BFS
Свойство DFS BFS
Структура данных Стек (явный или стек вызовов) Очередь
Стиль обхода Сначала вглубь, затем откат По слоям от источника
Асимптотика времени \(\Theta(V + E)\) со списками смежности \(\Theta(V + E)\) со списками смежности
Асимптотика времени \(\Theta(V^2)\) с матрицей смежности \(\Theta(V^2)\) с матрицей смежности
Кратчайшие пути В общем случае нет Да (только невзвешенный граф)
Поиск цикла Да (back edges) Менее прямолинейно
Топосорт Да (по finish time) Нет
Память \(O(V)\) глубина стека \(O(V)\) размер очереди
Доп. информация Времена обнаружения/завершения, типы рёбер Метки расстояний, BFS-дерево

На конечном графе оба метода полны, если запускать обход из каждой ещё не посещённой вершины: так обрабатываются все connected components. DFS удобен там, где нужна скобочная структура интервалов \([u.d,u.f]\) (циклы, топосорт, СКС). BFS — стандартный выбор для поуровневого расширения и минимального числа рёбер на пути.

1.7 Топологическая сортировка

DAG (directed acyclic graph) — ориентированный ациклический граф; моделирует предшествование.

Topological sort — линейный порядок вершин: для каждого \((u,v)\in E\) вершина \(u\) раньше \(v\).

Алгоритм: TOPOLOGICAL-SORT: запустить DFS, по мере finish time дописывать вершину в начало списка; время \(\Theta(V+E)\).

2. Определения

  • Graph \(G=(V,E)\): конечное \(V\) вершин и множество рёбер (неупорядованных или упорядованных пар).
  • Undirected graph: рёбра — неупорядованные пары \(\{u,v\}\) (симметрия).
  • Directed graph (digraph): рёбра — пары \((u,v)\) (асимметрия).
  • Weighted graph: каждому ребру сопоставлен числовой вес.
  • Adjacent: вершины смежны, если между ними есть ребро.
  • Path: последовательность вершин с рёбрами между соседними.
  • Simple path: путь без повторения вершин.
  • Cycle: путь с совпадающими началом и концом.
  • Connected component (неориентированный): максимальное множество попарно связанных вершин.
  • Sparse graph: \(|E|\ll|V|^2\).
  • Dense graph: \(|E|=\Theta(|V|^2)\).
  • Edge-list structure: списки вершин и рёбер с обратными указателями.
  • Adjacency list: у каждой вершины список инцидентных рёбер или соседей.
  • Adjacency matrix: матрица \(|V|\times|V|\) с кодированием рёбер.
  • DFS (depth-first search): обход «вглубь» со стеком или рекурсией.
  • BFS (breadth-first search): обход по уровням с очередью; кратчайшие расстояния в невзвешенном графе.
  • Discovery time \(u.d\): время первого обнаружения DFS (GRAY).
  • Finish time \(u.f\): время завершения обработки поддерева (BLACK).
  • Tree edge / Back edge / Forward edge / Cross edge: классификация рёбер DFS (см. курс CLRS).
  • BFS tree: остовное дерево рёбер BFS.
  • DAG: ориентированный граф без directed cycles.
  • Topological sort: линейный порядок вершин DAG с уважением ко всем рёбрам.

3. Формулы

  • DFS/BFS со списками смежности: \(\Theta(V+E)\)
  • С матрицей смежности: \(\Theta(V^2)\)
  • Handshaking lemma: \(\sum_{v\in V}\deg(v)=2|E|\) (неориентированный случай)
  • Максимум рёбер (неориентированный): \(0 \le |E| \le \dfrac{|V|(|V|-1)}{2}\)
  • Максимум рёбер (ориентированный): \(0 \le |E| \le |V|(|V|-1)\)
  • Parenthesis theorem — три варианта взаимного расположения интервалов DFS
  • Топосорт: порядок по убыванию \(v.f\)
  • После BFS(G,s): \(\delta(s,v)=v.d\) (невзвешенный случай)
  • Erdős–Rényi: \(\mathbb{E}[\deg(v)]=(|V|-1)p\), \(\mathbb{E}[|E|]=\binom{|V|}{2}p\)

4. Примеры и задания

4.1. Топологические порядки и удаляемые рёбра (Набор задач 10, Задание 1)

Рассмотрите DAG \(\mathcal{G}_1\) с вершинами \(A,\dots,H\) и рёбрами \(A\to B,C,D\); \(B\to D,F\); \(C\to D,G\); \(D\to E\); \(E\to F,G\); \(F,G\to H\) (тот же граф, что в парном файле недели). (a) перечислите все топопорядки; (b) рёбра, которые можно удалить, не меняя множества топопорядков; (c) максимум числа топопорядков на 9 вершинах; (d) максимум при \(|V|=7\), \(|E|=10\).

Нажмите, чтобы увидеть решение

(a) Ровно 4 порядка: свобода только в порядке \((B,C)\) и \((F,G)\) после \(A\), с фиксированными \(D,E,H\).

(b) Удаляемые без изменения множества порядков — транзитивные рёбра: \(A\to D\), \(B\to F\), \(C\to G\).

(c) Максимум \(9!\) при отсутствии рёбер.

(d) Максимум \(240=2!\cdot5!\) у полного двудольного DAG \(K_{2,5}\) с ориентацией от доли 2 к доле 5.

4.2. Вероятностный анализ структуры «BST смежности» (Набор задач 10, Задание 2)

Модель Erdős–Rényi; операции areAdjacent, removeEdge, removeVertex, iterateNeighbors — ожидаемые времена при worst-case BST.

Нажмите, чтобы увидеть решение

\(\mathbb{E}[|E|]=\binom{|V|}{2}p\); \(\mathbb{E}[\deg(v)]=(|V|-1)p\). Для операций со worst-case BST: areAdjacent — \(O(\mathbb{E}[\deg])\); removeEdge — \(O(\mathbb{E}[\deg])\); removeVertex — \(O((|V|-1)p(1+(|V|-2)p))\) в порядке величины; iterateNeighbors — \(\Theta(\mathbb{E}[\deg])\).

4.3. Дерево, недостижимое для BFS/DFS (Набор задач 10, Задание 3)

Построить пример слабо связного графа, остовного дерева \(T\) и корня \(r\), чтобы \(T\) не было ни BFS-, ни DFS-деревом от \(r\) ни при каком порядке смежности.

Нажмите, чтобы увидеть решение

Конструкция с \(V=\{r,a,b,c,d\}\), рёбрами \(r\to a,b,c,d\), \(a\to b\), \(a\to d\), \(b\to a\) и деревом \(T=\{r\to a,r\to b,r\to c,a\to d\}\): у BFS вершина \(d\) на расстоянии 1 из-за \(r\to d\), в \(T\) она ребёнок \(a\); у DFS \(b\) не может быть прямым ребёнком \(r\) из-за рёбер \(a\leftrightarrow b\). Дополнительно BFS-дерево отличается от любого DFS-дерева при любых порядках смежности.

4.4. Выбор представления (Лекция 10, Задание 1)
Нажмите, чтобы увидеть решение
  1. Плотный граф, частые запросы «есть ли ребро \((u,v)\)?» — матрица смежности (\(O(1)\) на запрос). 2. Разреженный социальный граф с обходом соседей — списки смежности. 3. Частые вставки/удаления рёбер по указателю на объект ребра — edge list с двусвязными списками и back-pointers.
4.5. Другой порядок BFS (Лекция 10, Задание 2)
Нажмите, чтобы увидеть решение

Множества слоёв \(L_0,\dots,L_3\) однозначны; меняется лишь порядок вершин внутри слоя при другом порядке постановки соседей в очередь.

4.6. Топосорт на маленьком DAG (Лекция 10, Задание 4)
Нажмите, чтобы увидеть решение

Для рёбер \((1,2),(1,3),(2,4),(3,4)\) допустимы оба порядка \(1,2,3,4\) и \(1,3,2,4\) — ответ не уникален.

4.7–4.8. Контрпримеры для DFS-времени (Лекция 10, Задания 5–6)
Нажмите, чтобы увидеть решение

Граф \(V=\{S,u,v\}\), \(E=\{S\to u,\; S\to v,\; u\to S\}\), порядок смежности \([u,v]\) у \(S\): есть путь \(u\to S\to v\), при этом \(u.d<v.d\), но \(v\) не потомок \(u\) в DFS-лесу; также \(v.d>u.f\), что опровергает наивные импликации.

4.9. Итеративный DFS (Лекция 10, Задание 7)
Нажмите, чтобы увидеть решение

Используют стек кадров \((v,i)\) — «вершина \(v\), следующий сосед — индекс \(i\)». При обработке WHITE-соседа кладут \((w,0)\) и увеличивают \(i\) в кадре \(v\); при исчерпании соседей кадр снимают и фиксируют \(v.f\).

DFS-ITERATIVE(G):
1  for each u in G.V:
2      u.color = WHITE;  u.π = NIL
3  time = 0
4  for each u in G.V:
5      if u.color == WHITE:
6          S = empty stack
7          push (u, 0) onto S
8          time = time + 1
9          u.d = time;  u.color = GRAY
10         while S not empty:
11             (v, i) = top of S
12             if i < |G.Adj[v]|:
13                 w = G.Adj[v][i]
14                 S.top = (v, i + 1)
15                 if w.color == WHITE:
16                     w.π = v;  w.color = GRAY
17                     time = time + 1;  w.d = time
18                     push (w, 0) onto S
19             else:
20                 pop S
21                 time = time + 1;  v.f = time;  v.color = BLACK